|
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree (the number of edges touching the vertex). In more colloquial terms, in a party of people some of whom shake hands, an even number of people must have shaken an odd number of other people's hands. The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma), : for a graph with vertex set ''V'' and edge set ''E''. Both results were proven by in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory. The vertices of odd degree in a graph are sometimes called odd nodes or odd vertices; in this terminology, the handshaking lemma can be restated as the statement that every graph has an even number of odd nodes. ==Proof== Euler's proof of the degree sum formula uses the technique of double counting: he counts the number of incident pairs (''v'',''e'') where ''e'' is an edge and vertex ''v'' is one of its endpoints, in two different ways. Vertex ''v'' belongs to deg(''v'') pairs, where deg(''v'') (the degree of ''v'') is the number of edges incident to it. Therefore the number of incident pairs is the sum of the degrees. However, each edge in the graph belongs to exactly two incident pairs, one for each of its endpoints; therefore, the number of incident pairs is 2|''E''|. Since these two formulas count the same set of objects, they must have equal values. In a sum of integers, the parity of the sum is not affected by the even terms in the sum; the overall sum is even when there is an even number of odd terms, and odd when there is an odd number of odd terms. Since one side of the degree sum formula is the even number 2|''E''|, the sum on the other side must have an even number of odd terms; that is, there must be an even number of odd-degree vertices. Alternatively, it is possible to use mathematical induction to prove that the number of odd-degree vertices is even, by removing one edge at a time from a given graph and using a case analysis on the degrees of its endpoints to determine the effect of this removal on the parity of the number of odd-degree vertices. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Handshaking lemma」の詳細全文を読む スポンサード リンク
|